import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 225. 用队列实现栈
 */
class MyStack {
    // 队列先进先出，栈先进后出
    Queue<Integer> qu1 ;
    Queue<Integer> qu2 ;

    public MyStack() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }
    
    public void push(int x) {
        //把入栈的 放进qu1
        if(!qu1.isEmpty()){
            qu1.offer(x);
        } else if (!qu2.isEmpty()) {
            qu2.offer(x);
        }else {

            qu1.offer(x);
        }
    }
    
    public int pop() {
        if(empty()){
            return -1;
        }
        //把有元素的队列转入size-1个元素到空队列，有元素的队列剩余的最后一个就是栈出的
        if(!qu1.isEmpty()){
            int size = qu1.size();
            for(int i = 0;i<size-1;i++){
                qu2.offer(qu1.poll());
            }
            return qu1.poll();
        }else{
            int size = qu2.size();
            for(int i = 0;i<size-1;i++){
                qu1.offer(qu2.poll());
            }
            return qu2.poll();
        }
    }
    //获取栈顶元素，不删除
    public int top() {
        if(empty()){
            return -1;
        }
        //把有元素的队列全部经中转后转入到空队列，
        if(!qu1.isEmpty()){
            int size = qu1.size();
            int ret = -1;
            for(int i = 0;i<size;i++){
                ret = qu1.poll();
                qu2.offer(ret);
            }
            return ret;
        }else{
            int size = qu2.size();
            int ret = -1;
            for(int i = 0;i<size;i++){
                ret = qu2.poll();
                qu1.offer(ret);
            }
            return ret;
        }
    }
    
    public boolean empty() {
        //两个队列都是空说明栈为空，返回true

        return  qu1.isEmpty() && qu2.isEmpty();
    }
}

/**
 * 232. 用栈实现队列
 */
class MyQueue {

    Stack<Integer> s1 ;
    Stack<Integer> s2 ;

    public MyQueue() {
        s1 = new Stack<>();//入队
        s2 = new Stack<>();//出队

    }

    public void push(int x) {
        s1.push(x);
    }

    public int pop() {
        if(!s2.empty()){
            return s2.pop();
        }
        if(!s1.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
            return s2.pop();
        }
        return -1;
    }

    public int peek() {
        if(s2.empty()){
            if(!s1.empty()){
                while(!s1.empty()){
                    s2.push(s1.pop());
                }
            }
        }
        if(!s2.empty()){
            return s2.peek();
        }
        return -1;

    }

    public boolean empty() {
        return s1.empty() && s2.empty();
    }
}